抛砖 | 老太太抛9枚硬币、总值1.7元，到底有几种硬币组合方式
作者 | 佚名、右手
插图 | 网络
编辑 | 八月
请听题
一个八旬老太登机时为了祈福，往飞机发动机里扔了一把硬币。机场工作人员发现后，将老太扣留并询问她扔了什么东西。
老太说，她扔进去了九枚硬币，因为九比较吉利，并且这些硬币价值1.7元人民币，但并不记得这些硬币的面额。
假设这些硬币可能存在的面值为1分、2分、5分、1角、5角、1元，请问老太太扔进去的九枚硬币存在几种可能的排列组合？
设：1分有a个，2分有b个，5分有c个，1角有d个，5角有e个，1元有f个。
那么应该满足如下条件：
1) 1a+2b+5c+10d+50e+100f=170.
2) a+b+c+d+e+f=9
且，abcdef均为整数且不能为负。
对于以上多元一次方程，解法有很多种，以我有限的数学知识，再加上搜索，可能存在的数学解法有：矩阵解法、克莱姆法则，规划求解。
上海某高中数学老师给出一个求解方法是数论，但他没空解答我的无聊问题。
EXCEL函数也是一种解法。
手工列举的方式，天然环保，我给出了三个组合，但如果遇到下次抛硬币的枚数不同或者面值不同，这种方法不能举一反三。
请教专业人士后，
杭州西溪的巴巴码农（感谢友商）给出一种C语言递归解法：
#include <stdio.h>
// 1.7 yuan
#define TARGET 170
#define MAX_COIN_NUM 9
int result = 0;
void calculate(int currMoney, int currCoin, int coinNum, int currResult[])
{
int i = 0;
//如果总钱数达到170，而且硬币数刚好是9，就满足条件，结果个数加1，并打印出详细结果
if (currMoney + currCoin == TARGET && coinNum == 9) {
for (i = 0; i < coinNum; i ++) {
printf ("%d ", currResult[i]);
}
printf("\n");
result++;
}
//如果总钱数超过170，或者硬币个数超过9，则肯定不符合目标，结束递归
if (currMoney + currCoin > TARGET || coinNum > 9)
return;
}
if (currCoin <= 1) {
int newResult[10];
for (i = 0; i < coinNum; i ++) {
newResult[i] = currResult[i];
}
newResult[i] = 1;
calculate(currMoney + currCoin, 1, coinNum + 1, newResult);
}
if (currCoin <= 2) {
int newResult[10];
for (i = 0; i < coinNum; i ++) {
newResult[i] = currResult[i];
}
newResult[i] = 2;
calculate(currMoney + currCoin, 2, coinNum + 1, newResult);
}
if (currCoin <= 5) {
int newResult[10];
for (i = 0; i < coinNum; i ++) {
newResult[i] = currResult[i];
}
newResult[i] = 5;
calculate(currMoney + currCoin, 5, coinNum + 1, newResult);
}
if (currCoin <= 10) {
int newResult[10];
for (i = 0; i < coinNum; i ++) {
newResult[i] = currResult[i];
}
newResult[i] = 10;
calculate(currMoney + currCoin, 10, coinNum + 1, newResult);
}
if (currCoin <= 50) {
int newResult[10];
for (i = 0; i < coinNum; i ++) {
newResult[i] = currResult[i];
}
newResult[i] = 50;
calculate(currMoney + currCoin, 50, coinNum + 1, newResult);
}
if (currCoin <= 100) {
int newResult[10];
for (i = 0; i < coinNum; i ++) {
newResult[i] = currResult[i];
}
newResult[i] = 100;
calculate(currMoney + currCoin, 100, coinNum + 1, newResult);
}
}
int main() {
int detailResult[10];
calculate(0, 0, 0, detailResult);
printf("Result:%d\n", result);
return 0;
}
他可能被老板发现在干一件不属于他的工作，没来得及跑出结果。
上海一位叫“右手”的码农同志（我喜欢他的名字）给出另一种求解方法。尽管他可以用多种语言求解，但考虑到正在被老板压榨，只能给出一种较为简单的代码求解方法。
他用的Python语言，代码如下：
import copy
sum_up = 170
coin_result = [0, 0, 0, 0, 0, 0, 0, 0, 0]
coin_value = [1, 2, 5, 10, 50, 100]
def cal(result):
sum = 0
for i in result:
sum += coin_value[i]
return sum
def list_all(max_coin, max_value):
a = []
for i in range(max_value):
a.append([i])
if max_coin == 1:
return a
after = list_all(max_coin - 1, max_value)
result = []
for i in a:
for j in after:
temp = []
temp.extend(i)
temp.extend(j)
result.append(temp)
return result
def join_result(result):
temp = []
result.sort()
for i in result:
temp.append(str(coin_value[i]))
return ",".join(temp)
def sample1():
to_write = open("result.txt", "w")
all_choice = list_all(9, 6)
exists = {}
for i in all_choice:
if cal(i) == 170:
r = join_result(i)
if not exists.has_key(r):
exists[r] = 1
print r
to_write.write(r)
to_write.write("\n")
to_write.close()
sample1()
回车
得出九种组合（数字很吉利）
1）1,1,1,1,1,5,10,50,100
2）1,1,1,2,5,5,5,50,100
3）1,1,1,2,5,10,50,50,50
4）1,1,2,2,2,2,10,50,100
5）1,2,2,5,5,5,50,50,50
6）2,2,2,2,2,5,5,50,100
7）2,2,2,2,2,10,50,50,50
8）5,5,10,10,10,10,10,10,100
9）10,10,10,10,10,10,10,50,50
学海无涯，古人诚不我欺也。
欢迎切磋。
本文经授权转载自公众号【没空有闲】，如需转载，请联系原作者。
点击文字链接，可查看以往的文章：